/**
 * @file DoubleLinkedList.h
 * @author 张奕欣 3190105655 (3190105655@zju.edu.cn)
 * @brief 实现双链表 list
 * @version 0.1
 * @date 2022-10-04
 * 
 * @copyright Copyright (c) 2022
 * 
 */
#include <iostream>
using namespace std;

template <typename Object>
class List{
    private:
    /**
     * @brief struct 私有内嵌节点声明，表示一种主要包含直接被存取而不是通过方法访问的数据的类
     *  Node类，该类由所储存的项、指向前一节点的指针、指向下一节点的指针以及构造函数组成。所有的数据成员是公有的。
     */
        struct Node
        {
            Object data;
            Node *prev; //prev 前指针
            Node *next;  //prev后指针

            Node( const Object &d = Object{}, Node *p = nullptr,
                                                Node *n = nullptr)
                : data{d}, prev{p}, next{n} {}
            
            Node( Object &&d, Node *p = nullptr,
                              Node *n = nullptr)
                : data{std::move(d)}, prev{p}, next{n} {}
        };

    public:
    /**
     * @brief 
     * 继承，iterator 具有和 const_iterator 完全相同的功能。
     */
        class const_iterator{
            public:
                const_iterator() : current{nullptr}
                {}
                /**
                 * @brief retrieve
                 * 
                 * @return const Object& 
                 */
                const Object & operator*() const 
                { return retrieve(); }

                /**
                 * @brief 前往下一个Node
                 * 
                 * @return const_iterator& 
                 */

                const_iterator & operator++ (){
                    current = current->next;
                    return *this;
                }
                
                /**
                 * @brief 前往下一个Node
                 * 
                 * @return const_iterator& 
                 */
                const_iterator operator++ (int){
                    const_iterator old = *this;
                    ++(*this);
                    return old;
                }
                /**
                 * @brief 前往上一个node
                 * 
                 * @return const_iterator 
                 */

                const_iterator operator--(){
                    current = current->prev;
                    return *this;
                }
                /**
                 * @brief 前往上一个node
                 * 
                 * @return const_iterator 
                 */

                const_iterator operator--(int){
                    const_iterator old = *this;
                    --(*this);
                    return old;
                }

                /**
                 * @brief 迭代器是否指向相同的节点
                 * 
                 * @param rhs 
                 * @return true 
                 * @return false 
                 */
                bool operator == (const const_iterator &rhs) const
                {return current == rhs.current;}
                /**
                 * @brief 迭代器是否指向不同的节点
                 * 
                 * @param rhs 
                 * @return true 
                 * @return false 
                 */
                bool operator != (const const_iterator &rhs) const
                {return !(*this == rhs);}

                protected:
                    Node *current;

                    Object & retrieve() const
                    {return current -> data;}

                    const_iterator(Node *p) 
                    : current{p}
                    {}

                    /**
                     * @brief friend 声明
                     * 赋予了list类访问const_iterator的非公有成员的权利
                     */

                    friend class List<Object>;
        };
        
        /**
         * @brief 继承
         * 当iterator类以这种方式写出时，继承了const_iterator类中所有的数据和方法。
         * 可以添加新的数据、新的方法，也可以覆盖现有方法。
         */
        class iterator : public const_iterator{
            public:
                iterator()
                {}

                Object &operator* ()
                {return const_iterator::retrieve();}
                const Object & operator*() const
                {return const_iterator::operator*();}

                iterator & operator++ (){
                    this ->current = this->current->next;
                    return *this;
                }

                iterator operator++(int){
                    iterator old = *this;
                    ++(*this);
                    return old;
                }

                iterator &operator--(){
                    this->current = this->current->prev;
                    return *this;
                }

                iterator operator--(int){
                    iterator old = *this;
                    --(*this);
                    return old;
                }

            protected:
                iterator(Node *p) : const_iterator{p}
                {}

                friend class List<Object>;
        };

    public:
    /**
     * @brief Construct a new List object
     * List的两个数据成员，即指向头结点的指针和指向尾结点的指针。
     * List类的其余部分由构造函数、五大函数以及一些方法组成。
     */

        List()
        {init();}

        /**
         * @brief Destroy the List object
         * 
         */
        ~List(){
            clear();
            delete head;
            delete tail;
        }

        /**
         * @brief Construct a new List object
         * 
         * @param rhs 
         */
        List(const List & rhs){
            init();
            for(auto & x: rhs)
                push_back(x);
        }
        /**
         * @brief copy
         * 
         * @param rhs 
         * @return List& 
         */
        List & operator = (const List & rhs){
            List copy = rhs;
            std::swap(*this, copy);
            return *this;
        }
        /**
         * @brief Construct a new List object
         * 
         * @param rhs 
         */
        List(List && rhs )
        : theSize{rhs.theSize}, head{rhs.head},tail{rhs.tail}{
            rhs.theSize = 0;
            rhs.head = nullptr;
            rhs.tail = nullptr;
        }
        /**
         * @brief swap
         * 
         * @param rhs 
         * @return List& 
         */
        List & operator = (List && rhs){
            std::swap(theSize, rhs.theSize);
            std::swap(head, rhs.head );
            std::swap(tail, rhs.tail );

            return *this;
        }

        /**
         * @brief 返回一个适当的迭代器，表示容器中的第一项
         * 
         * @return iterator 
         */
        iterator begin()
        {return iterator{head->next};}
        const_iterator begin() const
        {return const_iterator{head->next};}
        /**
         * @brief 返回一个适当的迭代器，表示容器中的尾端标记
         * 
         * @return iterator 
         */
        iterator end()
        {return iterator{tail};}
        const_iterator end() const
        {return const_iterator{tail};}

        /**
         * @brief 链表中节点数
         * 
         * @return int 
         */
        int size() const
        {return theSize;}
        /**
         * @brief 判断链表是否为空
         * 
         * @return true 
         * @return false 
         */
        bool empty() const
        {return size() == 0;}

        /**
         * @brief clear方法通过反复删除成员项直至list为空来完成清除工作。
         * 使用这种策略使得clear 避免染指回收节点的工作，因为节点的回收如今已经归入pop_front处理了
         */
        void clear(){
            while(!empty())
                pop_front();
        }

        /**
         * @brief 通过并使用适当的迭代器来工作
         * 
         * @return Object& 
         */
        Object & front()
        {return *begin();}
        /**
         * @brief 返回表的前端处的对象(还提供一个返回引用的修改函数)
         * 
         * @return const Object& 
         */
        const Object & front() const 
        {return *begin();}
        /**
         * @brief 返回表尾端处的对象
         * 
         * @return Object& 
         */

        Object &back()
        {return *--end();}
        const Object &back() const
        {return *--end();}

        /**
         * @brief 插入新元素在前端处
         * 
         * @param x 插入元素
         */
        void push_front(const Object & x)
        {insert(begin(),x);}
        /**
         * @brief 插入新元素在前端处，并删除
         * 
         * @param x 
         */
        void push_front(Object && x )
        {insert(begin(), std::move(x));}
        /**
         * @brief 把x添加到表的尾端
         * 
         * @param x 
         */
        void push_back(const Object & x) 
        {insert(end(), x);}
        /**
         * @brief 把x添加到表的尾端，并删除
         * 
         * @param x 
         */
        void push_back(Object && x)
        {insert(end, std::move(x));}
        /**
         * @brief 删除位于表的前端的对象
         * 
         */
        void pop_front()
        {erase(begin());}
        /**
         * @brief 删除位于表的尾端的对象
         * 
         */
        void pop_back()  
        {erase(--end());}

        // 在itr前插入x
        /**
         * @brief 把x添加到表中，由迭代器itr所给定的位置之前的位置上
         * 
         * @param itr 
         * @param x 新元素
         * @return iterator 指向被插入项的位置的一个迭代器
         */
        iterator insert(iterator itr, const Object & x ){
                Node *p = itr.current;
                theSize++;
                return {p->prev = p->prev->next = new Node{x, p->prev,p}};
        }

        //在itr前插入x
        /**
         * @brief 把x添加到表中，由迭代器itr所给定的位置之前的位置上，x待删除
         * 
         * @param itr 
         * @param x 
         * @return iterator 
         */
        iterator insert(iterator itr, Object && x){
            Node *p = itr.current;
            theSize++;
            return {p->prev = p->prev->next
                                    = new Node{std::move(x), p->prev,p } };
        }

        //删除在itr处的项
        /**
         * @brief 删除由迭代器所给定的位置上的对象
         * 
         * @param itr 
         * @return iterator 调用之前itr的后继元素所在的位置
         */
        iterator erase( iterator itr ){
            Node *p = itr.current; 
            iterator retVal{p->next};
            p->prev->next = p->next;
            p->next->prev = p->prev;
            delete p;
            theSize--;

            return retVal;
        }
        /**
         * @brief 删除从位置from开始到to(不包括)为止的所有项
         * 
         * @param from 
         * @param to 
         * @return iterator 
         */
        iterator erase(iterator from, iterator to ){
            for (iterator itr = from; itr != to;)
                itr = erase(itr);

            return to;
        }

        /**
         * @brief find 
         * 
         * @param x 
         * @return iterator 
        */ 
        iterator find(const Object &x) const{
            for (const_iterator itr = this->begin(); itr != this->end(); itr++)
                if (*itr == x){
                    cout << "True"<< " ";
                    cout << " at " << itr.current;
                    return itr.current;
                }
            cout << "False";
            return tail;
        } 

        /**
         * @brief print 所有的元素
         * 
         */
        void print() const{
            for (auto itr = this->begin(); itr != this->end();itr++){
                cout << *itr << " ";
            }
            cout << "\n";
        }

        /**
         * @brief print from到to的元素
         * 
         * @param from 
         * @param to 
         */
        void print(const const_iterator &from, const const_iterator &to){
            for (auto itr = from; itr != to; itr++){
                cout << *itr << " ";
            }
        }


    private:
        int theSize;
        Node *head;
        Node *tail;
        
        /**
         * @brief 创建一个空的List
         * 
         */
        void init(){
            theSize = 0;
            head = new Node;
            tail = new Node;
            head->next = tail;
            tail->prev = head;
        }

};

